P10859 [HBCPC2024] Nana Likes Polygons 题解

0x00 题目大意

给出平面上一些点，求以这些点的子集为顶点组成的凸多边形的面积的最小值。

0x01 解题思路

易证，最终的图形一定是一个三角形（如果是更多边形，必然可以削掉一块使得面积更小）。

看到数据范围：$1\le n\le 100$，完全可以 $O(n^3)$ 枚举三角形，求最小面积。

如何求三角形面积？可以用这个公式：

$S_{\Delta ABC}=\dfrac{|A.x\times B.y+B.x\times C.y+C.x\times A.y-A.x\times C.y-B.x\times A.y-C.x\times B.y|}{2}$

tips：不要用海伦公式，精度会炸。

如果三角形面积为 $0$，则说明当前三个点构不成三角形，如果所有组合面积都为 $0$，则无解。

0x02 AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct point{
    double x,y;
    friend double operator - (point _1,point _2){
        return sqrt((_1.x-_2.x)*(_1.x-_2.x)+(_1.y-_2.y)*(_1.y-_2.y));
    }
}a[1001];
double SS(point A,point B,point C){
//原来打算用海伦公式，结果炸了
    double AB=A-B,AC=A-C,BC=B-C;
    double p=(AB+AC+BC)/2.0;
    //cout<<"p="<<p<<endl;
    double x=p*(p-AB)*(p-BC)*(p-AC);
    if(x<=0)return 0;
    return sqrt(x);
}
double S(point A,point B,point C){
    return 0.5*fabs(A.x*B.y+B.x*C.y+C.x*A.y-A.x*C.y-B.x*A.y-C.x*B.y);
}
void solve(){
    double ans=-1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(i==j||j==k||i==k)continue;
                if(S(a[i],a[j],a[k])!=0){
                    if(ans!=-1)
                        ans=min(ans,S(a[i],a[j],a[k]));
                    else ans=S(a[i],a[j],a[k]);
                }
            }
        }
    }
    if(ans==-1)cout<<-1<<endl;
    else printf("%.8lf\n",ans);
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}